https://blog.naver.com/jqkt15/222031601969 [알고리즘] Counting Sort for Stable Sort - Pair Type (ppt, 소스코드) * 소스 코드 * blog.naver.com 1. stable counting sort 원소가 (첫번째 원소, 두번째 원소)의 튜플로 이루어졌을때, 이를 stable하게 counting sort하는 방법 https://deepdata.tistory.com/367 조건을 만족할때 매우 빠른 정렬 - counting sort 1. counting sort(카운팅 정렬) 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘 하지만 제한사항이 있다 정수나 정수..
1. 개요 선택 정렬은 실제 사용하기에는 매우 느린편이다. 그렇다면 다른 접근 방법은 없을까? "데이터를 하나씩 확인하면서 각 데이터를 적절한 위치에 삽입하면 어떨까?" 삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉽지만, 구현 난이도가 더 어려운데, 하지만 선택 정렬에 비해 실행 시간 측면에서 효율적이라고 알려져있다 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 "데이터가 거의 정렬되어 있을때" 매우 효율적이다 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면, 삽입 정렬은 그렇지 않다 삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬(insertion sort)이라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치..
1. 개요 인접한 두개의 원소를 비교하면서 자리를 계속 교환하면서 정렬하는 알고리즘 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동 한 단계가 끝나면, 가장 큰 원소가 마지막 자리로 이동함 교환하면서 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 부름 2. 예시를 통해 이해하는 버블 정렬 55, 7, 78, 12, 42를 정렬한다고 생각해보자. 먼저 55와 7을 비교하여, 55가 더 크니까 자리를 바꾼다. 다음 55와 78을 비교하여, 78이 더 크니까 자리를 바꾸지 않는다. 다음 78과 12를 비교하여 78이 더 크니까 자리를 바꾼다 마지막으로 78과 42를 비교하여, 78이 더 크니까 자리를 바꾼다. 그러면 배열에서 가장 큰 원소인 ..
1. 정렬(sorting) 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에, 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나 정렬 알고리즘으로 데이터를 정렬하면, 이진 탐색(binary search)이 가능해진다. 즉, 이진 탐색의 전처리 과정이기도 하다. 정렬을 공부하다보면 알고리즘의 효율성을 쉽게 이해할 수 있어 상황에 적절하지 못한 정렬 알고리즘을 이용하면, 당연히 프로그램은 비효율적으로 동작하면서, 필요 이상으로 시간을 많이 소요 여기 숫자 카드 10장이 있다. 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 어떻게 이 카드를 정렬할 수 있을까? 보통은 ..
1. 병합정렬(merge sort) 여러개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식 분할 정복 알고리즘을 활용함 주어진 자료를 최소 단위의 문제까지 나눈 다음에 차례대로 정렬해가면서 최종 결과를 얻어내는 방식 시간복잡도는 O(nlogn) 2. 개요 - 간단한 과정 - [69,10,30,2,16,8,31,22]를 병합정렬한다면?? 2-1) 분할과정 절반씩 자료를 왼쪽, 오른쪽으로 나눠가고 더 이상 쪼갤 수 없을때까지 반복해서 나눈다 2-2) 병합과정 가장 밑단의 왼쪽 부분집합과 오른쪽 부분집합의 원소 크기를 서로 비교하여 정렬하여 병합시키고, 최종 1개로 병합될때까지 반복함 3. 구현 길이가 1이면 정렬하지말고, 바로 return 길이가 1보다 크다면, 왼쪽과 오른쪽을 나눠준다..
1. counting sort(카운팅 정렬) 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘 하지만 제한사항이 있다 정수나 정수로 표현할 수 있는 자료에 대해서만 적용가능하다 - 각 항목의 발생 횟수를 기록하고자 정수로 인덱스 되는 카운팅 배열을 사용하기 때문 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야한다. 전제조건이 중요함 예를 들어 "0에서 1000이하의 정수이다" 이런 제한조건을 알고 있어야함 음수있으면 안된다는데.. 있어도 될것 같기는 한디 시간복잡도는 O(n+k)의 선형시간(n은 리스트의 길이, k는 정수의 최댓값) 2. 알고리즘 과정 2-1) 주어진 리스트에 등장하는 정수들이 각각 몇개 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
